package boardGenerator;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * Clase statica Solutions, desarrolla metodos para generar
 * soluciones a tableros sudokus, provee el metodo unicaSolucion
 * usado para saber si un tablero tiene solucion unica
 * metodo generar soluciones, genera las soluciones al problema
 * y metodo obtenerSoluciones obtiene todas las soluciones a un tablero
 */
public class Solutions {
    /*Soluciones al Tablero*/
    private static ArrayList<int[][]> solutions = new ArrayList<int[][]>();
    
    /**
     * Obtiene las soluciones de un tablero previamente generadas
     * @return 
     */
    public static ArrayList<int[][]> getSolutions(){
        return solutions;
    }
    
    /**
     * Informa si el tablero tiene solucion unica
     * @param orgProblemGrid
     * @return 
     */
    public static boolean hasUniqueSolution(int[][] orgProblemGrid) {
        solutions.clear();
        generateSolution(orgProblemGrid);
        return (solutions.size()==1);
    }
    
    
    /**
     * Genera todas las soluciones de un tablero Sudoku dado
     * @param orgProblemGrid 
     */
    public static void generateSolution(int[][] orgProblemGrid){      
        int[][] problemGrid = new int[9][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                problemGrid[i][j] = orgProblemGrid[i][j];
            }
        }
        ArrayList<Utils.CellData> problemCells = new ArrayList<Utils.CellData>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (problemGrid[i][j] == 0) {
                    Utils.CellData cell = new Utils.CellData(i, j);
                    cell.candidates = new ArrayList<Integer>(Arrays.asList(1,2, 3, 4, 5, 6, 7, 8, 9));
                    // remove candidates from the same column
                    for (int k = 0; k < 9; k++) {
                        if (problemGrid[k][j] != 0) {
                            cell.candidates.remove(Integer.valueOf(problemGrid[k][j]));
                        }
                    }
                    // remove candidates from the same row
                    for (int k = 0; k < 9; k++) {
                        if (problemGrid[i][k] != 0) {
                            cell.candidates.remove(Integer.valueOf(problemGrid[i][k]));
                        }
                    }
                    // remove candidates from the same cell
                    int HB = (int) i / 3;
                    int VB = (int) j / 3;
                    for (int k = HB * 3; k < (HB + 1) * 3; k++) {
                        for (int l = VB * 3; l < (VB + 1) * 3; l++) {
                            if (problemGrid[k][l] != 0) {
                                cell.candidates.remove(Integer.valueOf(problemGrid[k][l]));
                            }
                        }
                    }
                    problemCells.add(cell);
                }
            }
        }
        if (problemCells.size() == 1) {
            Utils.CellData cell = problemCells.get(0);
            if (cell.candidates.size() == 1) {
                problemGrid[cell.point.x][cell.point.y] = cell.candidates.get(0);
                solutions.add( problemGrid );
            }
            return;
        }
        int minCandidates = 10;
        int minIndex = -1;
        for (int i = 0; i < problemCells.size(); i++) {
            if (problemCells.get(i).candidates.size() < minCandidates) {
                minCandidates = problemCells.get(i).candidates.size();
                minIndex = i;
            }
        }
        if (minIndex > -1) {
            // pick the first candidate
            Utils.CellData cell = problemCells.get(minIndex);
            if (cell.candidates.size() > 0) {
                for (int i = 0; i < cell.candidates.size(); i++) {
                    int candidate = cell.candidates.get(i);
                    problemGrid[cell.point.x][cell.point.y] = candidate;
                    generateSolution(problemGrid);
                    // find more solutions if they exist by not continuing with the loop
                    problemGrid[cell.point.x][cell.point.y] = 0;
                }
            }
        }
    }
}
